The size of the global Routing Information Base (RIB) has been increasing at an alarming rate. This leads directly to rapid growth in the Forwarding Information Base (FIB) size. The growth in FIB size is particularly concerning because the FIB memory in line cards is much more expensive than regular memory modules in route processors. FIB memory in line cards needs to operate at much higher speeds, and it can be very costly to increase this memory capacity frequently (to match RIB size increases) for all routers in an Internet Service Provider (ISP). In addition, as the size of FIB memory increases, the FIB lookup time also may increase and the line card may require more power to operate.
One approach to reducing the impact of large FIBs is FIB caching, i.e., caching the most popular FIB entries in a fast-memory cache, while storing the full FIB in lower-cost, slower memory. However, there are a number of problems with FIB caching, the feasibility of which generally depends on how much locality is in the network traffic. Network links forward a huge number of packets every second, so even a 1% miss ratio can lead to millions of lookups per second in slow memory. This is an especially serious problem when a router starts with an empty cache, or when the cache needs to be filled without prior traffic information. Further, Internet forwarding uses longest-prefix match rather than exact match, so FIB caching often results in a cache-hiding problem where the packet's longest-prefix match in the FIB cache differs from that in the full FIB, and the packet thus is forwarded to the wrong next hop. In addition, prefixes and routes change periodically, and these changes may be implemented more slowly in the FIB cache than in the full FIB, again resulting in a cache-hiding problem.